package main

func main() {

}


type lruNode struct {
	pre *lruNode
	next *lruNode
	key int
	val int
}

type tlLruNode struct {
	cap int
	len int
	store map[int]*lruNode
	head *lruNode
	tail *lruNode
}

func initTlu(cap int) *tlLruNode {
	return &tlLruNode{
		cap:   cap,
		len:   0,
		store: map[int]*lruNode{},
		head:  nil,
		tail:  nil,
	}
}

func (s *tlLruNode)delete(key int)  {
	deleteNode,ok := s.store[key]
	if!ok{
		return
	}

	delete(s.store,key)
	if s.len == 1 {
		s.head = nil
		s.tail = nil
		s.len--
		return
	}

	if deleteNode.pre == nil {
		s.head = deleteNode.next
		s.head.pre = nil
	}else {
		deleteNode.pre.next = deleteNode.next
	}

	if deleteNode.next == nil {
		s.tail = deleteNode.pre
	}else {
		deleteNode.next.pre = deleteNode.pre
	}

}

func (s *tlLruNode) put(key,val int)  {
	_,ok := s.store[key]
	if ok {
		s.delete(key)
	}
	if s.len + 1 > s.cap {
		s.delete(s.tail.key)
	}
	node :=lruNode{
		key:  key,
		val:  val,
	}
	if s.len == 0 {
		s.tail = &node
		s.head = &node
		s.len = 1
		s.store[key] = &node
		return
	}
	node.next = s.head
	s.head.pre = &node
	s.head = &node
	s.store[key] = &node
	s.len++
}

func (s *tlLruNode)get(key int) int {
	node,ok := s.store[key]
	if !ok {
		return -1
	}

	s.delete(key)
	s.put(key,node.val)
	return node.val
}
